package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/19 07:12
 */
public class _1053 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(prevPermOpt1(new int[]{3,1,1,3})));
        System.out.println(Arrays.toString(prevPermOpt2(new int[]{3,1,1,3})));
    }
    public static int[] prevPermOpt1(int[] A) {
        boolean p = false;
        for(int i=0;i<A.length-1;i++){
            if(A[i+1]<A[i]){
                p=true;
                break;
            }
        }
        if(p){
            int swapLeft = Integer.MIN_VALUE;
            int swapIndex = 0;
            for(int i=A.length-1;i>=0;i--){
                int now = A[i];
                if(swapLeft==i){
                    int swap = A[swapLeft];
                    A[swapLeft] = A[swapIndex];
                    A[swapIndex] = swap;
                    return A;
                }
                for(int j=i-1;j>=0;j--){
                    if(A[j]>now){
                        if(swapLeft == j){
                            swapIndex=A[swapIndex]<=now?i:swapIndex;
                        }
                        if(swapLeft<j){
                            swapLeft = j;
                            swapIndex = i;
                        }
                        break;
                    }
                }
            }
        }
        return A;
    }



    public static int[] prevPermOpt2(int[] A) {
        int n = A.length;
        //从倒数第二位开始
        for(int i = n - 2;i >= 0;i--){
            int max = i + 1;
            for(int j = i + 1;j < n;j++){
                //找到 在i后面比它更小的，并且比i后面第一位值更大的
                //这句话是关键
                //找到A[i]后面最大的比它小的
                if(A[i] > A[j] && A[j] > A[max]){
                    max = j;
                }
            }
            //如果遇到，就直接交换
            if(A[i] > A[max]){
                int temp = A[i];
                A[i] = A[max];
                A[max] = temp;
                break;
            }
        }
        return A;
    }
}
